def merge(li,low,mid,high):
    i=low
    j=mid+1
    temp=[]
    #只要左右两边都有数
    while j<=high and i<=mid:
        if li[i]<=li[j]:
            temp.append(li[i])
            i+=1
        elif li[i]>li[j]:
            temp.append(li[j])
            j+=1
    #while执行完，两部分肯定有一部分没数了
    while i<=mid:
        temp.append(li[i])
        i+=1
    while j<=high:
        temp.append(li[j])
        j+=1
    li[low:high+1]=temp
    return temp


def merge_sort(li,low,high):
    #至少有两个元素
    if low<high: #至少有两个元素，递归
        mid=(low+high)//2
        merge_sort(li,low,mid)
        merge_sort(li,mid+1,high)
        merge(li,low,mid,high)
        print(li)
    return li
import random
li=[i for i in range(16)]
random.shuffle(li)
print(merge_sort(li,0,len(li)-1))
